|
Algorithms that construct convex hulls of various objects have a broad range of applications in mathematics and computer science. In computational geometry, numerous algorithms are proposed for computing the convex hull of a finite set of points, with various computational complexities. Computing the convex hull means that a non-ambiguous and efficient representation of the required convex shape is constructed. The complexity of the corresponding algorithms is usually estimated in terms of ''n'', the number of input points, and ''h'', the number of points on the convex hull. == Planar case == Consider the general case when the input to the algorithm is a finite unordered set of points on a Cartesian plane. An important special case in which the points are given in the order of traversal of a simple polygon's boundary is described later in a separate subsection. If not all points are on the same line, then their convex hull is a convex polygon whose vertices are some of the points in the input set. Its most common representation is the list of its vertices ordered along its boundary clockwise or counterclockwise. In some applications it is convenient to represent a convex polygon as an intersection of a set of half-planes. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Convex hull algorithms」の詳細全文を読む スポンサード リンク
|